class Solution(object):
    # 根据所有的数字都在1到n之前
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        left, right = 1, len(nums) - 1
        while (left < right):
            # 左右端点的情况通常用left < right作为终止条件
            mid = left + (right - left) / 2
            count = 0
            for num in nums:
                if num <= mid:
                    count += 1
            # print mid, count
            if count <= mid:
                left = mid + 1
            else:
                right = mid
        return left